2.Add Two Numbers [M]

题目：

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

思路：

题目的大意是两个链表求和，和也是一个链表（链表是逆序存的数字）
这和大数的加减很像，不过这个进位是从后向前。
所以可以同时从前往后加，然后保留进位。

其实做这种大数加减的题目不管是用的大数组还是链表，都是一样的：

  • 首先做个大循环，对每一位进行操作：

    • 当前位：(A[i]+B[i])%10
    • 进位：（A[i]+B[i]）/10

这里要注意一点，就是可能两个数组不是同样的长度，需要考虑一个数组已经到头，另一个数组还没结束的情况

代码

我的这个代码写的不够好，考虑的过于复杂，可以直接看下面更精巧的代码。

  1. /**
  2.  * Definition for singly-linked list->
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
  12.         //异常判断
  13.         if(l1 == NULL && l2 == NULL)
  14.             return NULL;
  15.         if(l1 == NULL)
  16.             return l2;
  17.         if(l2 == NULL)
  18.             return l1;  
  19.         //初始化
  20.         ListNode * result = new ListNode((l1->val + l2->val)%10);
  21.         int carry = (l1->val + l2->val)/10;  //表示进位
  22.         ListNode* templ1 = l1;
  23.         ListNode* templ2 = l2;
  24.         ListNode* tempresult = result;
  25.         //这里弄一个结束节点，有利于当一个节点到结尾后做操作
  26.         ListNode* EndNode = new ListNode(0);
  27.         while(templ1->next != NULL || templ2->next != NULL)
  28.         {
  29.             //如果某个链表已经到结尾了，那么就把它变成EndNode,特点是值为0,next = NULL
  30.             if(templ1->next == NULL)
  31.                 templ1 = EndNode;
  32.             else
  33.                 templ1 = templ1->next;
  34.             if(templ2->next == NULL)
  35.                 templ2 = EndNode;
  36.             else
  37.                 templ2 = templ2->next; 
  38.             tempresult->next = new ListNode((templ1->val + templ2->val + carry)%10);            
  39.             carry = (templ1->val + templ2->val + carry)/10;
  41.             tempresult = tempresult->next;
  43.         }
  44.         if(carry == 1)
  45.             tempresult->next = new ListNode(1);
  46.         return result;
  48.     }
  49. };

更精巧的代码

不得不说，potpie的这个代码比我上面的代码精简了不少，我上面的代码考虑的太多了，因为我通式用的templ1->val + templ2->val + carry，导致每次需要对先结束的链表进行尾部填充，而且开头多了很多额外的代码。

他的代码，2个链表是独立操作的，而且代码写的很精简，基本没废话！赞

  1. public class Solution {
  2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  3.         ListNode c1 = l1;
  4.         ListNode c2 = l2;
  5.         ListNode sentinel = new ListNode(0);
  6.         ListNode d = sentinel;
  7.         int sum = 0;
  8.         while (c1 != null || c2 != null) {
  9.             sum /= 10;
  10.             if (c1 != null) {
  11.                 sum += c1.val;
  12.                 c1 = c1.next;
  13.             }
  14.             if (c2 != null) {
  15.                 sum += c2.val;
  16.                 c2 = c2.next;
  17.             }
  18.             d.next = new ListNode(sum % 10);
  19.             d = d.next;
  20.         }
  21.         if (sum / 10 == 1)
  22.             d.next = new ListNode(1);
  23.         return sentinel.next;
  24.     }
  25. }